#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<map>
using namespace std;
int f[100001],ans,n,m,k,num[11];
int g[11][101];
string t;
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
int main()
{
	while(scanf("%d%d",&k,&n)&&(n!=0||k!=0))
	{
		map<string,int>mp;
		memset(num,0,sizeof(num));
		for(int i=1;i<=k;i++){cin>>t;mp[t]=i;}
		for(int i=1;i<=n;i++)
		{
			int tem;
			cin>>tem>>t;
			num[mp[t]]++;
			g[mp[t]][num[mp[t]]]=tem;
		}
		ans=0;	
		for(int i=1;i<=k;i++)
		{
			if(num[i]==0)continue;
			int sum=0,tem=0x3f3f3f3f;
			for(int p=1;p<=num[i];p++)sum+=g[i][p];
			memset(f,0,sizeof(f));
			f[0]=1;
			for(int p=1;p<=num[i];p++)
				for(int j=sum;j>=0;j--)
					if(j>=g[i][p])
					f[j]=max(f[j],f[j-g[i][p]]);
			for(int i=0;i<=sum;i++)
				if(f[i])tem=min(tem,max(i,sum-i));
			ans+=tem;
		}
		cout<<ans<<endl;
	}
	return 0;
}

